import collections
from typing import List


class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        letters = collections.Counter(letters)
        size = len(words)

        word_marks = []
        for word1 in words:
            mark = 0
            for ch1 in word1:
                mark += score[ord(ch1) - 97]
            word_marks.append(mark)

        def dfs(i, now):
            if i == size:
                return now

            # 选择当前词语
            res1 = 0
            word2 = words[i]
            have_letters = True
            for ch2 in word2:
                letters[ch2] -= 1
                if letters[ch2] < 0:
                    have_letters = False
            if have_letters:
                res1 = dfs(i + 1, now + word_marks[i])
            for ch2 in word2:
                letters[ch2] += 1

            # 不选择当前词语
            res2 = dfs(i + 1, now)
            return max(res1, res2)

        return dfs(0, 0)


if __name__ == "__main__":
    # 23
    print(Solution().maxScoreWords(words=["dog", "cat", "dad", "good"],
                                   letters=["a", "a", "c", "d", "d", "d", "g", "o", "o"],
                                   score=[1, 0, 9, 5, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                                          0]))

    # 27
    print(Solution().maxScoreWords(words=["xxxz", "ax", "bx", "cx"], letters=["z", "a", "b", "c", "x", "x", "x"],
                                   score=[4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0,
                                          10]))

    # 0
    print(Solution().maxScoreWords(words=["leetcode"], letters=["l", "e", "t", "c", "o", "d"],
                                   score=[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
                                          0]))
